#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX         1000        //  퍼즐 보드와 노드의 최대 개수
#define BSIZE       3           //  보드의 크기
#define DSIZE       4           //  퍼즐 조각이 움직일 수 있는 방향 수
#define DEPTH_LIMIT 6           //  depth limit

typedef char BOARD[3][3];
typedef struct node
{
    BOARD *pBoard;
    struct node *pParent;
    int numChildren;
}NODE;

typedef struct POINT
{
    int x;
    int y;
}POINT;

typedef struct  rdata
{
    int nextPointer;
    int prevMovement;
}RETURNDATA;

enum INDEX_NAMES { INITIAL = 0, GOAL = 99 };
enum DIRECTIONS { UP, DOWN, LEFT, RIGHT};

BOARD board[MAX];
BOARD goal = { {'1', '2', '3'}, {'8', 'B', '4'}, {'7', '6', '5'}};
NODE node[MAX];
int POINTER=0;
int visited[MAX];
int DEPTH=0;

void initialize(BOARD *b, NODE *n);
RETURNDATA expand(NODE *n, int prevMovement, RETURNDATA rd);
void nTravel(const NODE n, RETURNDATA *rd);
void _findNextMovements(const POINT p, int *direction, int prevMovement);
int _createChildren(NODE *n, int* direction, int ptr);
POINT _findB(const BOARD b);
void _copyBoard(const BOARD s, BOARD *t);
void _move(BOARD b, int direction);
void _swap(char* a, char* b);
void printBoard(BOARD b);
int compareBoard(const BOARD b, const BOARD goal);

int main(void)
{
    RETURNDATA rData = { INITIAL, -1 };
    int i;
    
    initialize(&board[INITIAL], &node[INITIAL]);
    printf("BOARD [0] : \n");
    printBoard(*node[INITIAL].pBoard);
    while(!compareBoard(*node[rData.nextPointer].pBoard, goal))
    {
        rData = expand(&node[rData.nextPointer], rData.prevMovement, rData);
        nTravel(node[rData.nextPointer], &rData);
        printf("\n\n");
        printf("BOARD [%i] : \n", rData.nextPointer);
        printBoard(*node[rData.nextPointer].pBoard);
    }
}

void initialize(BOARD *b, NODE *n)
{
    (*b)[0][0] = '2'; (*b)[0][1] = '8'; (*b)[0][2] = '3';
    (*b)[1][0] = '1'; (*b)[1][1] = '6'; (*b)[1][2] = '4';
    (*b)[2][0] = '7'; (*b)[2][1] = 'B'; (*b)[2][2] = '5';
    
    (*n).pBoard = b;
    (*n).pParent = 0;
}

RETURNDATA expand(NODE *n, int prevMovement, RETURNDATA rd)
{
    RETURNDATA data = rd;
    POINT pBlank = _findB(*n->pBoard);
    //int next;
    int direction[DSIZE] = {1, 1, 1, 1};
    int i;
    
    _findNextMovements(pBlank, direction, prevMovement);
    _createChildren(n, direction, POINTER);

    for(i=0;i<DSIZE;i++)    {   if(direction[i] == 1)   {   data.prevMovement = i; break;   }   }
    for(i=0;i<DSIZE;i++)    {   if(direction[i] == 1)   {   n->numChildren++;   }   }
    	
    return data;
}

void nTravel(const NODE n, RETURNDATA *rd)
{
    int i;
    if(POINTER == 0)
    {
        POINTER++;
        DEPTH++;
        visited[0] = 1;
        rd->nextPointer = POINTER;
        return;
    }
    
    for(i=0;i<n.numChildren;i++)
    {
        if(DEPTH == DEPTH_LIMIT)
        {
            POINTER -= n.pParent->numChildren + i;
            DEPTH--;
            break;
        }
        if(visited[POINTER+i] == 0)
        {
            visited[POINTER+i] = 1;
            POINTER += n.pParent->numChildren;
            DEPTH++;
            break;
        }
    }
    rd->nextPointer = POINTER;
}

void _findNextMovements(const POINT p, int *direction, int prevMovement)
{
    if(prevMovement == UP)      direction[DOWN] = 0;
    if(prevMovement == DOWN)    direction[UP] = 0;
    if(prevMovement == LEFT)    direction[RIGHT] = 0;
    if(prevMovement == RIGHT)   direction[LEFT] =0;

    if(p.x == 0)  direction[UP] = 0;
    if(p.x == 2)  direction[DOWN] = 0;
    if(p.y == 0)  direction[LEFT] = 0;
    if(p.y == 2)  direction[RIGHT] = 0;
}

int _createChildren(NODE *n, int* direction, int ptr)
{
    int i;
    int next;
    
    if(ptr == 0)    next = ++ptr;
    else            next = (ptr += n->pParent->numChildren);
    for(i=0;i<DSIZE;i++)
    {
        if(direction[i])
        {
            _copyBoard(*n->pBoard, &board[ptr]);
            _move(board[ptr], i);
            
            node[ptr].pBoard = &board[ptr];
            node[ptr].pParent = n;
            
            ptr++;
        }
    }
    return next;
}

POINT _findB(const BOARD b)
{
    POINT p;
    int i, j;
    
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            if(b[i][j] == 'B')
            {
                p.x = i;
                p.y = j;
                break;
            }
        }
    }
    return p;
}

void _copyBoard(const BOARD s, BOARD *t)
{
    int i, j;
    
    for(i=0;i<BSIZE;i++)
    {
        for(j=0;j<BSIZE;j++)    (*t)[i][j] = s[i][j];
    }
}

void _move(BOARD b, int direction)
{
    POINT p = _findB(b);
    
    switch(direction)
    {
        case UP:
            _swap(&b[p.x][p.y], &b[p.x-1][p.y]);
            break;
        case DOWN:
            _swap(&b[p.x][p.y], &b[p.x+1][p.y]);
            break;
        case LEFT:
            _swap(&b[p.x][p.y], &b[p.x][p.y-1]);
            break;
        case RIGHT:
            _swap(&b[p.x][p.y], &b[p.x][p.y+1]);
            break;
        default:
            break;
    }
}

void _swap(char* a, char* b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

void printBoard(BOARD b)
{
    int i, j;
    
    for(i=0;i<BSIZE;i++)
    {
        for(j=0;j<BSIZE;j++)    printf("\t%c", b[i][j]);
        printf("\n");
    }
}

int compareBoard(const BOARD b, const BOARD goal)
{
    int i, j;
    int flag;
    
    for(i=0;i<BSIZE;i++)
    {
        for(j=0;j<BSIZE;j++)
        {
            if(b[i][j] != goal[i][j])   {   flag = 0; break;    }
            else    flag = 1;
        }
        if(flag==0) break;
    }
    return flag;
}